Packing problems

The N-sphere in other dimensions can never be packed with complete efficiency in larger than one (in a one-dimensional universe, the circle analogue is just two points). That is, there will always be unused space if people are only packing circles. The most efficient way of packing circles, Circle packing, produces approximately 91% efficiency.

Tetrahedra and octahedra together can fill all of space in an arrangement known as the tetrahedral-octahedral honeycomb.

Simulations combining local improvement methods with random packings suggest that the lattice packings for icosahedra, dodecahedra, and octahedra are optimal in the broader class of all packings.

To show that this configuration is optimal, let $x\_1,\; \backslash dots,\; x\_k$ be the centers of disjoint open unit balls contained in a ball of radius centered at a point $x\_0$. Consider the map from the finite set $\backslash \{x\_1,\backslash dots,x\_k\backslash \}$ into $\backslash \{a\_1,\backslash dots,a\_k\backslash \}$ taking $x\_j$ in the corresponding $a\_j$ for each $1\; \backslash leq\; j\; \backslash leq\; k$. Since for all , $\backslash |a\_i-a\_j\backslash |\; =\; 2\backslash leq\backslash |x\_i-x\_j\backslash |$ this map is 1-Lipschitz and by the Kirszbraun theorem it extends to a 1-Lipschitz map that is globally defined; in particular, there exists a point $a\_0$ such that for all $1\backslash leq\; j\backslash leq\; k$ one has $\backslash |a\_0-a\_j\backslash |\; \backslash leq\; \backslash |x\_0-x\_j\backslash |$, so that also $r\_k\backslash leq\; 1+\backslash |a\_0-a\_j\backslash |\backslash leq\; 1+\backslash |x\_0-x\_j\backslash |\; \backslash leq\; r$. This shows that there are disjoint unit open balls in a ball of radius if and only if $r\; \backslash geq\; r\_k$. Notice that in an infinite-dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius if and only if $r\backslash geq\; 1+\backslash sqrt\{2\}$. For instance, the unit balls centered at $\backslash sqrt\{2\}e\_j$, where $\backslash \{e\_j\backslash \}\_j$ is an orthonormal basis, are disjoint and included in a ball of radius $1\; +\; \backslash sqrt\{2\}$ centered at the origin. Moreover, for , the maximum number of disjoint open unit balls inside a ball of radius is $$\backslash left\backslash lfloor\; \backslash frac\{2\}\{2-(r-1)^2\}\backslash right\backslash rfloor.$$

• Packing circles in a circle - closely related to spreading points in a unit circle with the objective of finding the greatest minimal separation, , between points. Optimal solutions have been proven for , and .
• Packing circles in a square - closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, , between points. To convert between these two formulations of the problem, the square side for unit circles will be $L\; =\; 2\; +\; 2/d\_n$. solutions have been proven for .
• Packing circles in a rectangle
• Packing circles in an isosceles right triangle - good estimates are known for .
• Packing circles in an equilateral triangle - Optimal solutions are known for , and are available for .

• Packing squares in a square: Optimal solutions have been proven for from 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100, and any square number integer. The wasted space is asymptotically .
• Packing squares in a circle: Good solutions are known for .

• Packing identical rectangles in a rectangle: The problem of packing multiple instances of a single rectangle of size , allowing for 90° rotation, in a bigger rectangle of size has some applications such as loading of boxes on pallets and, specifically, woodpulp stowage. For example, it is possible to pack 147 rectangles of size (137,95) in a rectangle of size (1600,1230).
• Packing different rectangles in a rectangle: The problem of packing multiple rectangles of varying widths and heights in an enclosing rectangle of minimum area (but with no boundaries on the enclosing rectangle's width or height) has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is NP-complete in general, but there are fast algorithms for solving small instances.

There are significant on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps:

An a × b rectangle can be packed with 1 × n strips if and only if n divides a or n divides b.

(1976). 9780883853023, The Mathematical Association of America. ISBN 9780883853023

de Bruijn's theorem: A box can be packed with a harmonic brick a × a b × a b c if the box has dimensions a p × a b q × a b c r for some p, q, r (i.e., the box is a multiple of the brick.)

The study of polyomino tilings largely concerns two classes of problems: to tile a rectangle with congruent tiles, and to pack one of each n-omino into a rectangle.

A classic puzzle of the second kind is to arrange all twelve into rectangles sized 3×20, 4×15, 5×12 or 6×10.

The problem of deciding whether a given set of can fit in a given square container has been shown to be complete for the existential theory of the reals..

• Bin packing problem
• Close-packing of equal spheres
• Conway puzzle
• Covering problem
• Cutting stock problem
• Ellipsoid packing
• Kissing number problem
• Knapsack problem
• Random close pack
• Set packing
• Slothouber–Graatsma puzzle
• Strip packing problem
• Tetrahedron packing
• Tetris

• Optimizing Three-Dimensional Bin Packing

Many puzzle books as well as mathematical journals contain articles on packing problems.

• Links to various MathWorld articles on packing
• MathWorld notes on packing squares.
• Erich's Packing Center
• www.packomania.com A site with tables, graphs, calculators, references, etc.
• "Box Packing" by Ed Pegg, Jr., the Wolfram Demonstrations Project, 2007.
• Best known packings of equal circles in a circle, up to 1100

• Circle packing challenge problem in Python